package hw2_TSP;

import ilog.concert.*;
import ilog.cplex.*;

public class RealAnswer {
	public static void main(String[] args) throws IloException{
		
		OrignData orignData = new OrignData();
		double[][] dataSet = orignData.data;
		int len = dataSet.length;
		int M = len+2;
		
		IloCplex model = new IloCplex();
	 	model.setParam(IloCplex.Param.RootAlgorithm, 1);//choose algorithm
		
		//define variables
		IloIntVar[][] x = new IloIntVar[len][len];
		IloIntVar[] u = new IloIntVar[len];
		u[0] = model.intVar(0, 0);
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++)
				x[i][j] = model.boolVar();
		}
		for (int i = 1; i < len; i++) {
			u[i] = model.intVar(2, len);
		}
		
		
		//objective
		IloLinearNumExpr z = model.linearNumExpr();
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (i == j)
					continue;
				double distance_x = dataSet[i][1]-dataSet[j][1];
				double distance_y = dataSet[i][2]-dataSet[j][2];
				z.addTerm(Math.sqrt(distance_x*distance_x + distance_y*distance_y), x[i][j]);
			}
		}
		model.addMinimize(z);
		
		//constraint1
		for (int i = 0; i < len; i++) {
			IloLinearIntExpr r1 = model.linearIntExpr();
			for (int j = 0; j < len; j++) {
				if(i==j)
					continue;
				r1.addTerm(1, x[i][j]);
			}
			model.addEq(r1, 1);
			
			IloLinearIntExpr r2 = model.linearIntExpr();
			for (int j = 0; j < len; j++) {
				if(i==j)
					continue;
				r2.addTerm(1, x[j][i]);
			}
			model.addEq(r2, 1);
			
			IloLinearIntExpr r3 = model.linearIntExpr();
			for (int j = 0; j < len; j++) {
				if(i==j)
					continue;
				r3.addTerm(1, x[i][j]);
				r3.addTerm(-1, x[j][i]);
			}
			model.addEq(r3, 0);
		}
		
		//constarint2
		for (int j = 1; j < len; j++)
			for (int i = 1; i < len; i++) {
				IloLinearIntExpr r = model.linearIntExpr();
				r.addTerm(1, u[j]);
				r.addTerm(-1, u[i]);
				r.addTerm(-M, x[i][j]);
				model.addGe(r, -M+1);
			}
		
		//solve problem
		if (model.solve()) {
			model.output().println("Solution status = " + model.getStatus());
			model.output().println("Solution value = " + model.getObjValue());
			for(int i=0; i<len; i++) {
				for(int j=0; j<len; j++) 
					if (i==j )
						continue;
					else if(model.getValue(x[i][j]) == 1)
						System.out.println("X[" + i + "," + j + "] = 1");
			}
		}
		model.close();
		
	}

}
